Programmable logic devices (PLDs), programmable logic arrays (PLAs), complex programmable logic devices (CPLDs), and field programmable gate arrays (FPGAs), (collectively referred to herein as “PLDs”) are well known devices that can be programmed by a user to implement user-defined logic functions. PLDs, as described and claimed in numerous patents assigned to Xilinx, Inc., assignee of the present invention, allow a user to configure and reconfigure the programmable elements on the PLD to implement various logic functions. Because of this versatility, the functionality implemented on a PLD can be updated as improvements in design and efficiency occur, without requiring new silicon. In general, a PLD can be reconfigured with an improved design, instead of designing a new device.
The design flow for PLDs typically includes a number of steps. A user prepares a circuit design using design entry tools such as a schematic capture tool or using a hardware description language (HDL), such as VHDL or Verilog. Particularly for more complex designs, HDLs are used to describe the architecture and behavior of discrete electronic systems. Once established, the circuit design is typically verified through simulation, e.g., behavioral simulation, to confirm that the circuit functions as intended. Further refinement and/or correction of the circuit design often results from this verification process.
The circuit design is then processed by a synthesis tool. The synthesis tool transforms the input design specification into a netlist which specifies the components of the design and the connectivity (signals) between the components. In the case of HDL based circuit designs, the synthesis tool converts the HDL code into a gate level implementation, optimizing the logic automatically for circuit size and speed. Further simulation can be performed at this point as part of the overall design verification process.
Next, the synthesized design is implemented. The implementation process can use a variety of tools such as structure analysis tools, place-and-route tools, etc. For example, a place-and-route tool can generate physical implementation data based on the input netlist and derived structure information. The implementation data specify specific resources that must be built or configured on the target device in order to implement the circuit design. The place-and-route tool can use the derived structure information to generate an improved placement. The design implementation process can take advantage of additional verification techniques. For example, functional simulation, static timing analysis, and timing simulation can all be used to analyze and refine the circuit. Once the design is implemented, a PLD device can be programmed based on the design.
One important part of the design synthesis process is to identify various circuit structures and logic elements in the circuit design and associate such structures and elements with pre-defined elements designed specifically for the target PLD architecture. This process of recognizing or inferring device primitives and macros allows a circuit designer to take advantage of design elements optimized for the particular PLD architecture without having to know detailed information about the best way to configure the basic logic blocks of the PLD. PLD manufacturers typically define various design elements that can be used by circuit designers including primitives (e.g., basic logical elements such as two input AND gates and two input OR gates), soft macros (e.g., schematics made by combining primitives and sometimes other soft macros), and relationally placed macros (RPMs) (e.g., soft macros that contain relative location constraint information, carry logic symbols, etc.). Note that the pre-defined elements designed for one or more target PLD architectures are variously referred to as “design elements” and “circuit design elements” in the present application.
Because any particular portion of the circuit design can be implemented in numerous logically equivalent ways, the synthesis process also aims to select the most appropriate (e.g., efficient, smallest, fastest, etc.) design elements with which to implement the design. The techniques used for such selection often depend on the type of logic device being used.
For example, circuits usually contain a large number of multiplexers. This is especially true for circuits that are automatically synthesized from high-level descriptions. Multiplexers exist in the datapaths of circuits where they are used to provide multiple connections between computation units. For example, multiplexers are typically used for routing the operands to the operators in the datapath. In CAD tools for high-level synthesis, multiplexers are also used to enable register sharing among several variables having non-overlapping lifetimes. During synthesis, multiplexers are often generated corresponding to the if-then-else and case statements present in HDL design descriptions. Moreover, cell libraries often contain various different choices of multiplexers, such as multiplexers with varying numbers of inputs and selectors, multiplexers having differences in physical implementation (e.g., passgate implementations, AND/OR gate implementations, etc.), and even circuits having equivalent functionality (e.g., lookup tables (LUTs)).
Accordingly, it is desirable to have systems, methods, software, and techniques for efficiently mapping multiplexers present in circuit designs to the various PLD design elements available for a particular PLD architecture.